__author__="ingulp"
__date__ ="$Mar 20, 2011 4:22:18 PM$"

from hexconfig import *
import random
from datahandler import *
from random import randint

PRINT_MOVE_FIND = False

BESTUTILITYRANGE = 0.05

NUM_THOUGHTS = 400
ORGANIZED_THOUGHTS = False

THOUGHTS_FOR_SIMILAR = 5

THOUGHT_LAYER_LIMIT = 3 # IT WILL NOT GO BEYOND ITS LIMIT OF DUMBNESS

class AIbot():
    def __init__(self, team=0,game = None,surf = None):
        self.team = team
        self.currentStateNode = None
        self.dataHandler = DataHandler()
        self.data = self.dataHandler.autoLoadDataSet(surf)
        
        self.bestIdeas = []
        self.bestIdeaUtils = []
        self.bestIdeaWeights = []
        self.ideaRating = -1
        self.world = game
        self.thinking = False

    def think(self,stateString,dazedList = []):
        self.thinking = True
        self.world.drawAll(self.world.screen)
        self.inCheck = False
        self.ideaRating = 1
        if self.thinkAboutChoices(stateString,dazedList) or THOUGHT_LAYER_LIMIT == 1:
            self.thinking = False
            return
        if not self.inCheck:
            self.ideaRating = 2
            if self.thinkAboutSimilarStates(stateString,dazedList) or THOUGHT_LAYER_LIMIT == 2:
                self.thinking = False
                return

        self.ideaRating = 2
        if self.thinkAboutSimilarStates(stateString,dazedList) or THOUGHT_LAYER_LIMIT == 2:
            self.thinking = False
            return

        self.ideaRating = 3
        if not self.inCheck:
            self.thinkAboutDerpDerp(stateString,dazedList)
        else:
            print "In check, going to Defensive Actions"
            self.getDefensiveActions(stateString, getDistToQueen(stateString, 1, 1)[0], dazedList)
        
    def decideEdgeFromBestIdeas(self, numBest = -1):
        edgeTotalUtilPairs = []
        if numBest == -1 or numBest > len(self.bestIdeas):
            numBest = len(self.bestIdeas)
        for i in range(numBest):
            utilTotal = self.bestIdeaUtils[i]#*self.bestIdeaUtils[i]
            #print "u", self.bestIdeaUtils[i]
            if i > 0:
                utilTotal += edgeTotalUtilPairs[i-1][1]
            edgeTotalUtilPairs.append((self.bestIdeas[i], utilTotal))
            
        #print numBest
        maxUtil = edgeTotalUtilPairs[numBest-1][1]
        #print "maxUtil", maxUtil
        randomUtil = random.random()*maxUtil
        returnIndex = 0
        for edgePair in edgeTotalUtilPairs:
            if edgePair[1]>= randomUtil:
                break
            returnIndex +=1

        print "I chose ", returnIndex, edgeTotalUtilPairs[returnIndex][0]
        return edgeTotalUtilPairs[returnIndex][0],returnIndex





    def thinkAboutChoices(self,stateString,dazedList = []):
        print "Green Phase"
        self.bestIdeas = []

        node = self.data.getNode(stateString)#assumes the node is in the dataset
        if node == None:
            #print "  Not in data: ", stateString
            self.data.addNode(stateString)
            self.data.spreadStateString(stateString)
            node = self.data.getNode(stateString)#assumes the node is in the dataset
        #print "thinking Before"
        self.currentStateNode = node                      #num_thoughts
        self.bestIdeas =  self.getBestUtilActionEdges(node,NUM_THOUGHTS,shuffle = not ORGANIZED_THOUGHTS,dazedList = dazedList)#10
        #print "thinking After"
        #for e in node.outEdges():
        #    self.bestIdeas.append(self.data.getEdgeFromKey(e))
        self.bestIdeaUtils = []
        self.bestIdeaWeights = []
        for i in self.bestIdeas:

            #if unit is dazed:
            #   if trying to push an enemy unit
            #       continue
            
            nextNode = stateStringFromActionList(self.currentStateNode.stateString(),i.a)
            #print "nextNode", self.data.getNode(nextNode)
            self.bestIdeaUtils.append(self.data.getNode(nextNode).util())#there is no reason there shouldnt already be a node
            self.bestIdeaWeights.append(self.data.getNode(nextNode).w)
        #print "done making best ideas list"
        #print "BEST IDEAS:", len(self.bestIdeas)
        #self.inCheck = False
        if self.couldStateBeInCheck(stateString, 0):
            #print stateString, "might be in check,",
            if self.data.isStateInCheck(stateString, 0):
                #print "and is"
                self.inCheck = True
            else:
                pass
                #print "and isn't"
        #print "done with inCheck check"
        if not self.inCheck and self.bestIdeaUtils[0] == 0.0:
            return False
            #self.thinkAboutSimilarStates(stateString, dazedList, 100)

        #print "BEST IDEAS:",
        #for e in node.outEdges():
        #    self.bestIdeas.append(self.data.getEdgeFromKey(e))
        
        return True

    def thinkAboutSimilarStates(self, stateString, dazedList):
        print " Yellow Phase"
        similarNodes = []
        similarNodes.extend(self.data.getSimilarStates(stateString))
        #for key in self.data.nodes.p0Keys[getP0KeyString(stateString)].keys():
        #    if key != stateString:
        #        self.similarNodes.append(key)

        print "   number of similar states: ", len(similarNodes)
        if len(similarNodes) > 0:
            sortedNodes = sorted([self.data.getNode(n) for n in similarNodes], reverse=True)

            possibleIdeas = []
            possibleUtils = []
            possibleWeight = []

            for similarNode in sortedNodes:
                #if similarNode.util() <= 0.0: continue
                bestEdgesFromNode =  self.getBestUtilActionEdges(similarNode, THOUGHTS_FOR_SIMILAR, \
                                            shuffle= not ORGANIZED_THOUGHTS, dazedList = dazedList)
                bestIdeasActionLists = [edge.a for edge in bestEdgesFromNode]

                newBestIdeas = []
                for e in self.bestIdeas:
                    #print e
                    if e.a in bestIdeasActionLists:
                        #print "   possible action:", e.a
                        newBestIdeas.append(e)
                
                if newBestIdeas ==[]:
                    #print "  ", similarNode.stateString(), "didn't have enough data 1"
                    continue

                """for i in range(len(newBestIdeas)):
                    if self.data.getNode(stateStringFromActionList(similarNode.stateString(),newBestIdeas[i].a)).util() > 0.0:
                        print "i: ", i, self.data.getNode(stateStringFromActionList(similarNode.stateString(),newBestIdeas[i].a)).util()"""

                """# Check if first of the edges have utility.  If not, none do!
                if self.data.getNode(stateStringFromActionList(similarNode.stateString,newBestIdeas[0].a)).util() == 0.0:
                    endNodeString = stateStringFromActionList(stateString,newBestIdeas[0].a)
                    print "  ", endNodeString, "didn't have enough data to tell me anything 2"
                    continue"""

                # There's some utility, add all those with it
                for edge in newBestIdeas:
                    similarEndNode = self.data.getNode(stateStringFromActionList(similarNode.stateString(), edge.a))
                    #print similarEndNode.util()
                    if similarEndNode.util() > 0.0:
                        if edge in possibleIdeas:
                            ind = possibleIdeas.index(edge)
                            possibleUtils[ind] += similarEndNode.u
                            possibleWeight[ind] += similarEndNode.w
                        else:
                            possibleIdeas.append(edge)
                            possibleUtils.append(similarEndNode.u)
                            possibleWeight.append(similarEndNode.w)
                    
            if len(possibleIdeas) > 0:
                self.bestIdeas = possibleIdeas
                self.bestIdeaUtils = []
                for i in range(len(possibleUtils)):
                    self.bestIdeaUtils.append(possibleUtils[i] / possibleWeight[i])
                    #print self.bestIdeaUtils[i],"=",possibleUtils[i],"/",possibleWeight[i]
                print "I have some ideas!!!"
                return True
        return False

    def walkTowardsLoc(self,loc1,loc2):
        dif = (loc2[0]-loc1[0],loc2[1]-loc1[1],loc2[2]-loc1[2])
        disps = [0,0,0]


        disps[0] = loc2[0]-loc1[0]
        disps[1] = loc2[0]-loc1[0]
        disps[2] = loc2[0]-loc1[0]
        maxval = -1
        maxdir = 0
        tielist = []
        for dir in HEXDIRECTIONS:
            val =0
            for i in range(3):
                if disps[i]>0 and dir[i]>0:
                    val+=1
                if disps[i]<0 and dir[i]<0:
                    val+=1
                if disps[i] == 0 and disps[i] == 0:
                    val+=1

            if val>maxval:
                maxval = val
                maxdir = dir
                tielist = []
                #if there is a nice math function to check signage equivalence it could be used here as well
            if val == maxval:
                if not maxdir in tielist:
                    tielist.append(maxdir)
                tielist.append(dir)

        if not tielist == []:
            movedir = random.choice(tielist)
        else:
            movedir = maxdir

        return movedir


    def thinkAboutDerpDerp(self, stateString, dazedList):
        #distToEnemyQueen,aggroLocs = getDistToQueen(stateString, 0,0)
        print "Red Phase"
        distToEnemyQueen = getDistToQueen(stateString, 0, 0)[0]
        distTuple =  getDistToQueen(stateString, 1, 1)
        distToFriendlyQueen = distTuple[0]
        aggroLocs = distTuple[1]
        self.aggressorEnemies = []
        
        if distToEnemyQueen < distToFriendlyQueen:
            return self.getOffensiveActions(stateString, distToEnemyQueen, dazedList)
        elif distToEnemyQueen > distToFriendlyQueen:
            for a in aggroLocs:
                self.aggressorEnemies.append(a)
            return self.getDefensiveActions(stateString, distToFriendlyQueen, dazedList)
        elif random.randint(0,1)==0:
            return self.getOffensiveActions(stateString, distToEnemyQueen, dazedList)
        return self.getDefensiveActions(stateString, distToFriendlyQueen, dazedList)

    def getDefensiveActions(self, stateString, currentDist, dazedList):
        print "  Hangin' back!"
        if self.getDefensiveWarps(stateString): return True
        
        dThrowTriples =  self.getDefensiveThrows(stateString, currentDist, dazedList)
        dPushTriples =  self.getDefensivePushes(stateString, currentDist, dazedList)
        dMoveTriples = self.getDefensiveMoves(stateString, currentDist)
        bestTriples = []
        #print [oWarpTriples, oThrowTriples, oPushTriples, oMoveTriples]
        for array in [[], dThrowTriples, dPushTriples, dMoveTriples]:
            bestTriples.extend(array)
        #print "middle", len(self.bestIdeas)
        if len(bestTriples) == 0:
            return False

        bestTriples = sorted(bestTriples, key=lambda triple:triple[1], reverse=True)

        self.bestIdeas = []
        self.bestIdeaUtils = []
        self.bestIdeaWeights = []
        for bestTriple in bestTriples:
            self.bestIdeas.append(bestTriple[0])
            self.bestIdeaUtils.append(bestTriple[1])
            self.bestIdeaWeights.append(bestTriple[2])
        #print "after", len(self.bestIdeas)
        return True
        
    def getOffensiveActions(self, stateString, currentDist, dazedList):
        print "  Goin' on the offensive!"
        oWarpTriples = self.getOffensiveWarps(stateString, currentDist)
        oThrowTriples = self.getOffensiveThrows(stateString, dazedList, currentDist)
        oPushTriples = self.getOffensivePushes(stateString, dazedList, currentDist)
        oMoveTriples = self.getOffensiveMoves(stateString, currentDist)
        bestTriples = []
        #print [oWarpTriples, oThrowTriples, oPushTriples, oMoveTriples]
        for array in [oWarpTriples, oThrowTriples, oPushTriples, oMoveTriples]:
            bestTriples.extend(array)
        #print "middle", len(self.bestIdeas)
        if len(bestTriples) == 0:
            return False
        
        bestTriples = sorted(bestTriples, key=lambda triple:triple[1], reverse=True)

        self.bestIdeas = []
        self.bestIdeaUtils = []
        self.bestIdeaWeights = []
        for bestTriple in bestTriples:
            self.bestIdeas.append(bestTriple[0])
            self.bestIdeaUtils.append(bestTriple[1])
            self.bestIdeaWeights.append(bestTriple[2])
        #print "after", len(self.bestIdeas)
        return True

    def getOffensiveWarps(self, stateString, currentDist):
        print "    warps?"
        ref = REFLIST_P0 if self.team==0 else REFLIST_P1

        newBestIdeas = []
        for move in self.bestIdeas:
            if move.a[len(move.a)-1][1] == 'W':
                newState = stateStringFromActionList(stateString, move.a)
                dist = getDistToQueen(newState, 0, 0)[0]
                diff = currentDist - dist
                newBestIdeas.append((move, diff, dist))

        if len(newBestIdeas)==0:
            return []

        newBestIdeas = sorted(newBestIdeas, key=lambda pair:pair[1], reverse=True)
        if newBestIdeas[0][1]<=0.0:
            return []


        return newBestIdeas
        

    def getOffensiveThrows(self, stateString, dazedList, currentDist):
        print "    throws?"
        myDist = currentDist
        edgeValPairs = []
        for bestEdge in self.bestIdeas:
            isThrow = False
            if bestEdge.a[0][1]=="T":
                isThrow = True
            elif len(bestEdge.a)>1 and (bestEdge.a[1][1] == "T"):
                if not bestEdge.a[0][1] == "P":
                    if dazedList.count(int(bestEdge.a[0][2:4])) == 0:
                        isThrow = True

            if isThrow:
                newDist = getDistToQueen(stateStringFromActionList(stateString, bestEdge.a),0,0)[0]
                if  myDist- newDist > 0:
                    edgeValPairs.append((bestEdge, myDist-newDist, newDist))

        if len(edgeValPairs) == 0:
            return []

        edgeValPairs = sorted(edgeValPairs, key=lambda pair: pair[1],reverse = True)
        #print edgeValPairs
        
        #self.bestIdeaUtils[0] = 666.0
        print "throws!"
        return edgeValPairs


        #for endState in
    def getOffensiveMoves(self,stateString, currentDist):
        print "    moves?"
        myDist = currentDist
        edgeValPairs = []
        for bestEdge in self.bestIdeas:

            if (bestEdge.a[0][1] == "M") and len(bestEdge.a)==1:

                newDist = getDistToQueen(stateStringFromActionList(stateString, bestEdge.a),0,0)[0]
                if  myDist- newDist > 0:
                    edgeValPairs.append((bestEdge, myDist-newDist, newDist))

        if len(edgeValPairs) == 0:
            return []

        edgeValPairs = sorted(edgeValPairs, key=lambda pair: pair[1],reverse = True)
        #print edgeValPairs
        #self.bestIdeas = []
        #self.bestIdeaUtils = []
        
        #self.bestIdeaUtils[0] = 666.0
        print "moves!"
        return edgeValPairs

    def getOffensivePushes(self,stateString,dazedList, currentDist):
        print "    pushes?"
        myDist = currentDist
        edgeValPairs = []
        for bestEdge in self.bestIdeas:

            if (bestEdge.a[0][1] == "P") and len(bestEdge.a)==1 and dazedList.count(int(bestEdge.a[0][2:4])) == 0:

                newDist = getDistToQueen(stateStringFromActionList(stateString, bestEdge.a),0,0)[0]
                if  myDist- newDist > 0:
                    edgeValPairs.append((bestEdge, (myDist-newDist), newDist))

        if len(edgeValPairs) == 0:
            return []

        edgeValPairs = sorted(edgeValPairs, key=lambda pair: pair[1],reverse = True)
        #print edgeValPairs
        #self.bestIdeas = []
        #self.bestIdeaUtils = []

        #self.bestIdeaUtils[0] = 666.0
        print "pushes!"
        return edgeValPairs

    def getDefensiveWarps(self, stateString):
        print "gettin' warps!"
        ref = REFLIST_P0 if self.team==0 else REFLIST_P1
        queenRef = stateString.index('A')
        queenLoc = ref[queenRef]

        dist = 999.0
        close_i = -1
        for i in range(len(WARPLOCATIONS)):
            check = dist3(queenLoc, WARPLOCATIONS[i])
            if check < dist:
                dist = check
                close_i = i

        if close_i == -1: return False
        
        warpRefs = [ ref.index( WARPLOCATIONS[close_i-2] ),
                     ref.index( WARPLOCATIONS[close_i-1] ),
                     ref.index( WARPLOCATIONS[close_i] ),
                     ref.index( WARPLOCATIONS[(close_i+1)%len(WARPLOCATIONS)] ),
                     ref.index( WARPLOCATIONS[(close_i+2)%len(WARPLOCATIONS)] )]

        desirableWarpRefs = []
        dontMoveWarpRefs  = []
        if (stateString[warpRefs[1]]=='1' or stateString[warpRefs[3]]=='1'):
                                                        # if enemy at 1 cw or 1 ccw
            if not stateString[warpRefs[2]]=='0':       #    if not already blocked
                desirableWarpRefs.append(warpRefs[2])   #       Wanna block it!
            else:                                       #    already blocked?
                dontMoveWarpRefs.append(warpRefs[2])    #       Don't wanna unblock it!
        if stateString[warpRefs[0]]=='1':               # if enemy two cw
            if not stateString[warpRefs[1]]=='0':       #    if not already blocked
                desirableWarpRefs.append(warpRefs[1])   #       Wanna block it!
            else:                                       #    already blocked?
                dontMoveWarpRefs.append(warpRefs[1])    #       Don't wanna unblock it!
        if stateString[warpRefs[4]]=='1':               # if enemy two ccw
            if not stateString[warpRefs[3]]=='0':       #    if not already blocked
                desirableWarpRefs.append(warpRefs[3])   #       Wanna block it!
            else:                                       #    already blocked?
                dontMoveWarpRefs.append(warpRefs[3])    #       Don't wanna unblock it!

        possible = []
        for move in self.bestIdeas:
            if len(move.a)==1:
                if int(move.a[0][2:4]) in dontMoveWarpRefs: continue
                if move.a[0][1]=='P': ref_i = int(move.a[0][6:8])
                else:                 ref_i = int(move.a[0][4:6])
            else:
                if int(move.a[0][2:4]) in dontMoveWarpRefs: continue
                ref_i = int(move.a[len(move.a)-1][4:6])
            if ref_i in desirableWarpRefs:
                possible.append(move)

        if len(possible) == 0:
            return False

        self.bestIdeas = possible
        self.bestIdeaUtils = []
        self.bestIdeaWeights = []
        for i in range(len(self.bestIdeas)):
            self.bestIdeaUtils.append(1.0)
            self.bestIdeaWeights.append(1.0)
        return True

    def getDefensiveThrows(self, stateString, currentDist, dazedList):
        print "defensive throws!"
        possible = []
        for out in self.data.nodes[stateString].outEdges():
            endState = out[-43:]
            dist = getDistToQueen(endState, 1, 0)[0]
            diff = currentDist - dist
            if diff < 0.0:
                edge = self.data.getEdgeFromKey(out)
                lastInd = len(edge.a)-1
                if not edge.a[lastInd][1]=='T': continue
                if not stateString[int(edge.a[lastInd][2:4])]=='1': continue
                if edge.a[0][1]=='P' and not self.isDazeLegalPush(stateString, edge.a, dazedList): continue
                possible.append((edge, dist, diff))

        if len(possible) == 0: return []

        possible = sorted(possible, key=lambda triple: triple[1],reverse = True)
        return possible
    
    def getDefensivePushes(self, stateString, currentDist, dazedList):
        print "defensive pushes!"
        possible = []
        for out in self.data.nodes[stateString].outEdges():
            endState = out[-43:]
            dist = getDistToQueen(endState, 1, 0)[0]
            diff = currentDist - dist
            if diff < 0.0:
                edge = self.data.getEdgeFromKey(out)
                if not edge.a[0][1]=='P' or \
                   not edge.a[0][4:6] or \
                   not self.isDazeLegalPush(stateString, edge.a, dazedList):
                    continue
                if not stateString[int(edge.a[0][4:6])]=='1': continue
                possible.append((edge, dist, diff))

        if len(possible) == 0: return []
        
        possible = sorted(possible, key=lambda triple: triple[1],reverse = True)
        return possible


    def getDefensiveMoves(self,stateString, currentDist):
        lowest = 999.0
        #This should
        #self.aggressorEnemies
        print "    moves?"
        print self.aggressorEnemies
        if self.aggressorEnemies == []:
            print "Josh, why aren't you passing any aggressorEnemies to this function?!?!?!?!?!"
            return []
        queenRef = stateString.index("A")
        qLoc= REFLIST_P0[queenRef]#THIS IS NOT 2 PLAYER FRIENDLY
        eLoc = REFLIST_P0[self.aggressorEnemies[0]]
        

        avgLoc = ((eLoc[0]-qLoc[0])/2.0,(eLoc[1]-qLoc[1])/2.0,(eLoc[2]-qLoc[2])/2.0)
        avgLoc = (avgLoc[0]+qLoc[0],avgLoc[1]+qLoc[1],avgLoc[2]+qLoc[2])
        #avgLoc = ((qLoc[0]-eLoc[0])/2.0,(qLoc[1]-eLoc[1])/2.0,(qLoc[2]-eLoc[2])/2.0)
        #print qLoc,avgLoc,eLoc
        #if (int(avgLoc),int())
        #print avgLoc
        myDist = getCloseUnitsToSpot(stateString,avgLoc ,0,0)
        #print myDist
        edgeValPairs = []
        for bestEdge in self.bestIdeas:
            if (bestEdge.a[0][1] == "M") and len(bestEdge.a)==1:

                newDist = getCloseUnitsToSpot(stateStringFromActionList(stateString,bestEdge.a)\
                        ,avgLoc,0,0)
                if  myDist- newDist > 0:
                    edgeValPairs.append((bestEdge, (myDist-newDist), newDist))


        if len(edgeValPairs) == 0:
            print "EMPTY"
            return []

        edgeValPairs = sorted(edgeValPairs, key=lambda pair: pair[1],reverse = True)
        #print edgeValPairs
        return edgeValPairs
    def isLocSuicide(self,ref):
        print isKillSpot()

    def isDazeLegalPush(self, stateString, actionList, listofIndices):
        legal = True
        if actionList[0][1] == "P":
            #print "Doing a push"
            if int(actionList[0][2:4]) in listofIndices:
                #print "doing a push with a dazed unit"
                #print stateString[int(actionList[0][4:6])]
                if stateString[int(actionList[0][4:6])] == "1":
                    #print "doing a push with a dazed unit againt an enemy"
                    legal = False
        return legal

    def decideAction(self,stateString, lookAhead = False, lookAheadSpread = 5):
        print "Deciding Action:", stateString
        winnable, bestUtilMove =  self.data.isStateWinnable(stateString)
        print winnable, bestUtilMove, stateStringFromActionList(stateString, bestUtilMove)
        node = self.data.getNode(stateString)#assumes the node is in the dataset

        self.currentStateNode = node
        if winnable:
            retList= []
            for a in bestUtilMove:
                retList.append(a)
            return retList

        edges = self.getBestUtilActionEdges(self.currentStateNode, lookAheadSpread)
        zerocheck = [self.data.getNode(edge.n[1]).util() != 0.0 for edge in edges]

        if True in zerocheck:
            edgesForNodes = [self.getBestUtilActionEdges(self.data.getNode(edges[n].n[1]), lookAheadSpread) for n in range(len(edges)) ]
            utils = []
            for n in range(len(edgesForNodes)):
                edgeUtils = []
                for e in range(len(edgesForNodes[n])):
                    newNode = self.data.getNode(edgesForNodes[n][e].n[1])
                    #
                    newEdges = self.getBestUtilActionEdges(newNode, lookAheadSpread)
                    sum = 0.0
                    for edge in newEdges:
                        sum += self.data.getNode(edge.n[1]).util()
                    edgeUtils.append(sum/len(newEdges) if len(newEdges)>0 else 0)

                sum = 0.0
                for e in range(len(edgeUtils)):
                    sum += edgeUtils[e]
                utils.append(sum/len(edgesForNodes[n]))
            bestUtil = -2.0
            index = -1
            for n in range(len(utils)):
                if utils[n] >= bestUtil:
                    index = n
                    bestUtil = utils[n]
            for e in range(len(edges)):
                print e,":", edges[e], "Util:", self.data.getNode(edges[e].n[1]).util(), "Lookahead:", utils[e]

            retList= []
            for a in edge.a:
                retList.append(a)
            return retList

        
        

    def pickRandomMove(self, state):
        moves = getAllMovesFromState(state,self.team)

        return moves[random.randint(0,len(moves)-1)]

    def singleNodeShift(self,node,shift):
        print "I'm adding a single node shift"
        print "   ", node.stateString(), shift
        node.addUtil((node.util()+shift)*node.w,0.1)

    

    def getBestUtilActionEdges(self,node,numBest, inCheck = False,shuffle = True,dazedList = []):
        #print "getBestUtilActionEdges"
        if node.stateString()[0] == "W":
            print "This node is a win node", node
            return []
       
        n = node
        # teamKilledByActionList
        self.data.spreadStateNode(n)

        edgeNodePairs = []

        allMovesCheck = True
        #print "outEdges:", len(n.outEdges())
        for edgeKey in n.outEdges():
            #print " edge:",edgeKey
            edge = self.data.edges[edgeKey]
            if not self.isDazeLegalPush(edge.n[0],edge.a,dazedList):
                continue
                    
            #IF you are going to kill your own unit. NOT A BEST MOVE of any sort
            teamKilled = teamKilledByActionList(edge.n[0],edge.a)
            copyNodeList = []
            if teamKilled == 0:
                #print "         TEAM 0 KILLED",edge
                continue
            elif teamKilled == 1:
                #print "         TEAM 1 KILLED",edge
                #create copyNode that is not in dataSet
                copyNode = self.data.getNode(edge.n[1]).copy()

                copyNode.addUtil(0.25,1.0)#THIS IS THE KILLING ENEMY
                
                if self.data.getNode(edge.n[1]).w == 1.0:
                    print "WAHT",edge.a
                    self.singleNodeShift(self.data.getNode(edge.n[1]), 0.25)#to non-zero it at least

                edgeNodePairs.append([edge,copyNode])
                continue


            edgeNodePairs.append([edge,self.data.getNode(edge.n[1])])
            #edgeNodePairs.append([edge,self.data.getNode(edge.n[1])])
            #AUTO_WIN IS TAKEN CARE OF BECAUSE UTIL WILL BE MAX
            
        #if allMovesCheck:
        #    singleton = []
        #    singleton.append(self.data.getEdgeFromKey((random.choice(n.outEdges()))))
        #    return singleton


        if shuffle:
            random.shuffle(edgeNodePairs)
        edgeNodePairs = sorted(edgeNodePairs, key=lambda pair: pair[1],reverse = True)

        returnEdgeNodePairs = []
        nodesNotInCheck = 0
        for edgeNodePair in edgeNodePairs:
            nodeString = edgeNodePair[1].stateString()
            if nodeString.find("B")!= -1 and nodesNotInCheck <= 3 and self.couldStateBeInCheck(nodeString, 0):
                #print nodeString, "might be in check,",
                if self.data.isStateInCheck(nodeString, 0):
                    #print "and is."
                    continue
                else:
                    #print "and isn't."
                    print "  ",edgeNodePair[0].a
                    allMovesCheck = False
                    nodesNotInCheck += 1
                    returnEdgeNodePairs.append(edgeNodePair)
            else:
                if nodesNotInCheck <= 3:
                    pass
                    #print nodeString, "will not result in check"
                allMovesCheck = False
                nodesNotInCheck += 1
                returnEdgeNodePairs.append(edgeNodePair)
            if nodesNotInCheck >= numBest:
                break

        if returnEdgeNodePairs == []:
            print "!!!!I'm pretty sure you're in checkmate!!!!"
            returnEdgeNodePairs = edgeNodePairs
        edges = []
        for p in returnEdgeNodePairs:
            edges.append(p[0])

        #print "Done get best util action edges"
        return edges
        #retList = []
        #for e in edges:
        #    retList.append(e)
    
    def chooseNextState(self):
        pass

    def addDataForState(self, state):
        print "     Adding data for state", state
        moveList = getAllMovesFromState(state, self.team)
        print "       moves =", moveList
        for m in moveList:
            self.addToData(state, stateStringFromActionList(state, m), m)

    def addToData(self,state1,state2,moveList):
        self.data.addEdge(state1, state2, moveList)

    def takeTurn(self):
        pass

    def saveData(self):
        self.dataHandler.autoSaveDataSet(self.data)


    def couldStateBeInCheck(self, stateString,turn):
        #print "Checking if ", stateString, "is in check"
        if stateString.find("A") == -1:
            return True
        p0units, p1units, p0king, p1king = stateStringToBoard(stateString, turn)
        danger = []
        blocking = []

        enemies = p1units if turn == 0 else p0units
        allies = p0units if turn == 0 else p1units

        for a in allies:
            blocking.append(a.hexloc)

        for e in enemies:
            #danger.extend(self.getAvailableWalkLocations(e))
            danger.append(e.hexloc)

        queen = p0king if turn  == 0 else p1king
        
        unitLoc = queen.hexloc
        inDanger = False

        locsToCheck = []
        for i in range(6):
            dir = HEXDIRECTIONS[i]
            newLoc1 = (unitLoc[0]+dir[0], unitLoc[1]+dir[1], unitLoc[2]+dir[2])
            newLoc2 = (unitLoc[0]+dir[0]*2, unitLoc[1]+dir[1]*2, unitLoc[2]+dir[2]*2)
            if newLoc1 in danger:
                return True
            elif not newLoc1 in blocking:
                if newLoc2 in danger:
                    return True
                else:
                    total = 0
                    for d in range(len(HEXDIRECTIONS)):
                        if d >= 4 and total < 1:
                            break
                        dir = HEXDIRECTIONS[d]
                        loc = (newLoc2[0]+dir[0],newLoc2[1]+dir[1],newLoc2[2]+dir[2])
                        if isLocOnBoard(loc, turn) and loc in danger:
                            total += 1

                        if total >= 3:
                            return True


            #locsToCheck.append(newLoc1)
            #locsToCheck.append(newLoc2)
        #print "It is not in check"
        return False
    def trainWithReplay(self, replay):
        print "Training with replay"
        clock = pygame.time.Clock()
        clock.tick()
        screen = pygame.display.set_mode((SWIDTH,SHEIGHT))#,pygame.FULLSCREEN)#,pygame.HWSURFACE)

        currentState = replay.setups
        endBoardStates = [[] for i in range(2)]
        turn = 0
        propogationList = []
        print "replay setup", replay.setups
        print "move list", replay.moveList
        for e in replay.moveList:

            #print "adding move"

            nextState = stateStringFromActionList(currentState,e)
            print nextState
            endBoardStates[turn].append(nextState)

            if nextState[0] == "W":
                propogationList.append((endBoardStates[turn][:-1], 1.0))
                propogationList.append((endBoardStates[1 if turn == 0 else 0][-3:], -1.0))
                self.data.addEdge(currentState, nextState, e)
                currentState = nextState
                break
            unitTeam = teamKilledByActionList(currentState,e)
            if unitTeam==0:
                propogationList.append((endBoardStates[turn][-2:], -.5))
                propogationList.append((endBoardStates[1 if turn == 0 else 0][-4:],  .5))
            elif unitTeam==1:
                propogationList.append((endBoardStates[turn][-4:],  .5))
                propogationList.append((endBoardStates[1 if turn == 0 else 0][-2:], -.5))

            self.data.addEdge(currentState, nextState, e)
            currentState = nextState


            currentState = switchStateStringToOtherTeam(currentState, turn)
            turn = (turn+1)%2

            #currentState = boardToStateString(p0units, p1units, p0king, p1king, turn)
            #print currentState
        print "end: ", endBoardStates
        ms = clock.tick()
        secs = ms/1000
        mins = secs/60
        print
        print "TIME TO ADD DATA:",mins,"mins,",secs%60 if secs>60 else secs,"secs"
        print "NODES_LENGTH",len(self.data.nodes)
        print "EDGES_LENGTH",len(self.data.edges)



        print "spreading replays"
        

        statesToSpread = []
        for i in range(len(endBoardStates)):
            for state in endBoardStates[i]:
                statesToSpread.append(state)

        for key in statesToSpread:
            #print ds.nodes[key]
            self.data.spreadStateString(key, 0)

        ms = clock.tick()
        secs = ms/1000
        mins = secs/60
        print
        print "TIME TO SPREAD DATA:",mins,"mins,",secs%60 if secs>60 else secs,"secs"
        print "NODES_LENGTH",len(self.data.nodes)
        print "EDGES_LENGTH",len(self.data.edges)


        for prop in propogationList:
            self.data.propogateUtil(prop[0], prop[1])

        for i in range(len(endBoardStates)):
            if i == 0:
                continue
            for endStateString in endBoardStates[i]:
                print endStateString
                node = self.data.getNode(endStateString)
                node.addUtil((node.util()+0.1)*node.w,0.1)

        ms = clock.tick()
        secs = ms/1000
        mins = secs/60
        print
        print "TIME TO PROPOGATE UTIL: ",mins,"mins,",secs%60 if secs>60 else secs,"secs"
        print "NODES_LENGTH",len(self.data.nodes)
        print "EDGES_LENGTH",len(self.data.edges)
            
        """
        print "UTIL PROPOGATION PRINTOUTS:"
        numWithUtil = 0
        for k in ds.nodes.keys():
            if not ds.nodes[k].util()==0.0:
                numWithUtil+=1
                #print ds.nodes[k].util(), ds.nodes[k].stateString(), ds.nodes[k].w
        print "  ", numWithUtil, "/", len(ds.nodes.keys()), "nodes have utility"
        """

if __name__ == "__main__":
    pygame.init()
    screen = pygame.display.set_mode((SWIDTH,SHEIGHT))#,pygame.FULLSCREEN)#,pygame.HWSURFACE)
    clock = pygame.time.Clock()
    ai = AIbot(0)
    stateString = '-----0-1----0-10011-A-B-00110-1----0-1-----'
    ai.data.spreadStateString(stateString)
    print ai.data.getEdgeFromKey(stateString+"--0--0-1------100-1-A-B-0011-01----0-1-----")
    #print ai.isStateLegalPush(stateString, ["0P303740"],[30])
    #getAllMovesFromState(stateString)
    #ai.decideAction(stateString)
    #print ai.currentStateNode
    